package com.origin.niuke.dfs;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/4/19 13:55
 * 给定一个用 n*m 矩阵表示的群岛的地图，其中 1 表示岛屿， 0 表示海洋，
 * 每个岛屿的水平或竖直方向相邻的岛屿可以视为连在一起的岛屿，每一块岛屿视为面积为 1 ，
 * 请问面积最大的岛屿是多少。
 * 算法：深度优先搜索
 * 从一个岛屿位置开始，分别向上下左右搜索，看能形成的岛屿，并记录岛屿的面积
 */
public class 岛屿的最大面积 {

    int n, m;
    int[][] grid;

    public int maxAreaIsland(int[][] _grid) {
        grid = _grid;
        n = grid.length;
        m = grid[0].length;
        int ans = 0;
        boolean[][] flag = new boolean[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) ans = Math.max(ans, dfs(i, j, flag));
        return ans;
    }

    int[][] directs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    int dfs(int i, int j, boolean[][] flag) {
        int res = 0;
        if (i < 0 || i >= n || j < 0 || j >= m) return res;
        if (flag[i][j]) return res;
        if (grid[i][j] == 0) return res;
        ++res;
        flag[i][j] = true;
        for (int[] direct : directs) res += dfs(i + direct[0], j + direct[1], flag);
        return res;
    }

}
